package graph;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Queue;

/*
 *@description 腐烂的橘子
 *@author hkfan
 *@version 1.0
 *@create 2025/5/19 10:28
 */
public class LeetCode_994 {

    @Test
    public void test(){
        int[][] grid = new int[][]{
                {2,1},
                {1,0}
        };
        System.out.println(orangesRotting(grid));
    }

    class Node{
        int i;
        int j;

        public Node(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

    public int orangesRotting(int[][] grid) {
        //1. 定义
        int res = 0;
        Queue<Node> queue = new ArrayDeque<>();
        int[][] visited = new int[grid.length][grid[0].length];
        //2. 逐个遍历，记录第一层
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j]==2){
                    //res=1;
                    visited[i][j]=1;
                    queue.add(new Node(i,j));
                }
            }
        }
        //3. 逐层感染
        boolean flag= false;
        while (!queue.isEmpty()){
            flag=true;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node temp = queue.poll();
                visit(grid,visited,temp.i,temp.j,queue);
            }
            res++;
        }

        //4. 最后判断
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j]==1){
                    return -1;
                }
            }
        }
        return (flag)?res-1:res;
    }

    private void visit(int[][] grid, int[][] visited, int i, int j, Queue<Node> queue) {
        visited[i][j]=1;
        if (i>=1 && grid[i-1][j]==1 && visited[i-1][j]==0){
            grid[i-1][j]=2;
            visited[i-1][j]=1;
            queue.add(new Node(i-1,j));
        }
        if (j>=1 && grid[i][j-1]==1 && visited[i][j-1]==0){
            grid[i][j-1]=2;
            visited[i][j-1]=1;
            queue.add(new Node(i,j-1));
        }
        if (i<=grid.length-2 && grid[i+1][j]==1 && visited[i+1][j]==0){
            grid[i+1][j]=2;
            visited[i+1][j]=1;
            queue.add(new Node(i+1,j));
        }
        if (j<=grid[0].length-2 && grid[i][j+1]==1 && visited[i][j+1]==0){
            grid[i][j+1]=2;
            visited[i][j+1]=1;
            queue.add(new Node(i,j+1));
        }

    }


}
